package site.wanjiahao;

import com.sun.istack.internal.NotNull;
import site.wanjiahao.printer.BinaryTreeInfo;

import javax.swing.tree.TreeNode;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

// 前序遍历: 打印二叉树
// 中序遍历：元素降序或者升序
// 后序遍历: 先子节点后父节点操作
public class BinarySearchTree<E> implements BinaryTreeInfo {

    // 容量大小
    private int size;

    // 指向根节点
    private Node<E> root;

    private final Comparator<E> comparator;

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public BinarySearchTree() {
        this(null);
    }

    public void add(E ele) {
        if (root == null) {
            // 添加root节点
            root = new Node<>(ele, null);
        } else {
            Node<E> cur = root;
            Node<E> parent = null;
            int flag = 0;
            while (cur != null) {
                int compareRes = comparator(cur.ele, ele);
                if (compareRes > 0) {
                    parent = cur;
                    cur = cur.left;
                    flag = 0;
                } else if (compareRes < 0) {
                    parent = cur;
                    cur = cur.right;
                    flag = 1;
                } else {
                    // 覆盖处理，ele可能为引用类型，更加符合实际情况
                    cur.ele = ele;
                    size++;
                    return;
                }
            }
            if (flag == 0) {
                parent.left = new Node<>(ele, parent);
            } else {
                parent.right = new Node<>(ele, parent);
            }
        }

        size++;
    }

    public int comparator(E e1, E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        // 直接强制转换，默认实现比较接口
        return ((Comparable<E>) e1).compareTo(e2);
    }

    // 前序遍历
    public void preorderTraversal(Consumer<E> consumer) {
        if (consumer == null) return;
        preorderTraversal(root, consumer);
    }

    public void preorderTraversal(Node<E> node, Consumer<E> consumer) {
        // 1.递归出口
        if (node == null) return;
        if (consumer.isStop) return;
        // 外部自自定义消费逻辑
        consumer.isStop = consumer.accept(node.ele);

        // 明确函数作用是什么，遍历当前拿到的节点
        preorderTraversal(node.left, consumer);
        preorderTraversal(node.right,  consumer);
    }

    // 中序遍历
    public void inorderTraversal(Consumer<E> consumer) {
        if (consumer == null) return;
        inorderTraversal(root, consumer);
    }

    public void inorderTraversal(Node<E> node, Consumer<E> consumer) {
        // 1.递归出口
        if (node == null || consumer.isStop) return;
        inorderTraversal(node.left, consumer);
        if (consumer.isStop) return;
        consumer.isStop = consumer.accept(node.ele);
        // 明确函数作用是什么，遍历当前拿到的节点
        inorderTraversal(node.right, consumer);
    }

    // 后序遍历
    public void postorderTraversal(Consumer<E> consumer) {
        postorderTraversal(root, consumer);
    }

    public void postorderTraversal(Node<E> node, Consumer<E> consumer) {
        // 1.递归出口
        if (node == null || consumer.isStop) return;

        // 明确函数作用是什么，遍历当前拿到的节点
        postorderTraversal(node.left, consumer);
        postorderTraversal(node.right, consumer);
        if (consumer.isStop) return;
        consumer.isStop = consumer.accept(node.ele);
    }

    // 层序遍历
    public void levelOrderTraversal(Consumer<E> consumer) {
        // 遍历完每一层，如何遍历完每一层，将读出的数据放入队列中
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();

            boolean isInterrupt = consumer.accept(node.ele);
            if (isInterrupt) return;

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    // 计算二叉树的高度，采用层序遍历，可以计算二叉树的高度
    public int height() {
        if (root == null) return 0;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        int levelSize = 1;
        int height = 0;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }

            if (levelSize == 0) {
                // 当前层遍历完成
                levelSize = queue.size();
                height++;
            }
        }
        return height;
    }

    // 判断一个二叉树是否为完全二叉树
    public boolean isComplete() {
        boolean isLeaf = false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();

            if (isLeaf && (node.left != null || node.right != null)) return false;

            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                // 左子树为空，右子树不为空，肯定不是完全二叉树
                return false;
            } else {
                // 左书不为空，右树为空，叶子节点判断
                isLeaf = true;
            }

            if (node.right != null) {
                queue.offer(node.right);
            } else {
                // 判断后续节点是否存在叶子节点，存在则不是完成二叉树，不存在者是
                isLeaf = true;
            }
        }
        return true;
    }

    // 前驱节点
    private Node<E> predecessor(Node<E> node) {
        // 当前节点是否有左节点
        if (node.left != null) {
            node = node.left;
            while (node.right != null) {
                node = node.right;
            }
            // 循环终止，当前节点为前驱节点
            return node;
        } else if (node.parent != null) {
            // 父节点的右节点为当前节点，则为前驱节点
            while (node.parent != null && node.parent.right != node) {
                node = node.parent;
            }
            return node.parent;
        } else {
            // 左节点也为空，父节点为空，无前驱节点
            return null;
        }
    }

    // 后继节点
    private Node<E> successor(Node<E> node) {
        // 当前节点是否有左节点
        if (node.right != null) {
            node = node.right;
            while (node.left != null) {
                node = node.left;
            }
            // 循环终止，当前节点为前驱节点
            return node;
        } else if (node.parent != null) {
            // 父节点的右节点为当前节点，则为前驱节点
            while (node.parent != null && node.parent.left != node) {
                node = node.parent;
            }
            return node.parent;
        } else {
            // 左节点也为空，父节点为空，无前驱节点
            return null;
        }
    }

    public void remove(E ele) {
        // 判断当前节点的度
        Node<E> node = node(ele);

        if (hasTwoChildren(node)) {
            // 度为2：先找到对应的前驱（后继）节点，覆盖删除的节点，然后在删除对应的前驱（后继）节点（只存在度为1或者度为2）
            Node<E> predecessor = predecessor(node);
            // predecessor不存在为空
            node.ele = predecessor.ele;
            node = predecessor;
        }

        // 度为1：当前节点为父节点的什么节点，当前节点的子节点，作为这个节点存在
        Node<E> replacement = node.left != null? node.left: node.right;
        if (replacement != null) {
            replacement.parent = node.parent;
            if (node.parent != null) {
                if (node.parent.right == node) {
                    // 右节点
                    node.parent.right = replacement;
                } else {
                    // 左节点
                    node.parent.left = replacement;
                }
            } else {
                root = replacement;
            }
        }  else {
            // 度为0：直接删除
            if (node.parent != null) {
                if (node.parent.left == node) {
                    node.parent.left = null;
                } else {
                    node.parent.right = null;
                }
            } else {
                root = null;
            }
        }
        size--;
    }

    public boolean contains(E ele) {
        return node(ele) != null;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        root = null;
        size = 0;
    }

    // 根据元素值，获取节点对象
    public Node<E> node(E ele) {
        Node<E> node = root;
        while (node != null) {
            int comp = comparator(node.ele, ele);
            if (comp > 0) {
                // 左边
                node = node.left;
            } else if (comp < 0) {
                // 右边
                node = node.right;
            } else {
                return node;
            }
        }
        return null;
    }

    private boolean hasTwoChildren(Node<E> node) {
        return node.left != null && node.right != null;
    }

    private boolean nonChildren(Node<E> node) {
        return node.left == null || node.right == null;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        toString(root, sb, "");
        return sb.toString();
    }

    public void toString(Node<E> node, StringBuffer sb, String prefix) {
        if (node == null) return;
        sb.append(prefix).append(": ").append(node.ele).append("\n");
        toString(node.left, sb, prefix + "--" + "L");
        toString(node.right, sb, prefix + "--" + "R");
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        return ((Node<E>) node).ele;
    }

    // 消费者类
    public static abstract class Consumer<E> {

        boolean isStop;

        abstract boolean accept(E e);

    }

    // 内部使用的Node类
    private static class Node<E> {

        private E ele;

        private Node<E> left;

        private Node<E> right;

        private Node<E> parent;

        public Node(E ele, Node<E> parent) {
            this.ele = ele;
            this.parent = parent;
        }
    }

}
